Search Results

Documents authored by Marchetti-Spaccamela, Alberto

Document
DOI: 10.4230/LIPIcs.ECRTS.2023.3
The Safe and Effective Use of Low-Assurance Predictions in Safety-Critical Systems

Authors: Kunal Agrawal, Sanjoy Baruah, Michael A. Bender, and Alberto Marchetti-Spaccamela

Published in: LIPIcs, Volume 262, 35th Euromicro Conference on Real-Time Systems (ECRTS 2023)

Abstract
The algorithm-design paradigm of algorithms using predictions is explored as a means of incorporating the computations of lower-assurance components (such as machine-learning based ones) into safety-critical systems that must have their correctness validated to very high levels of assurance. The paradigm is applied to two simple example applications that are relevant to the real-time systems community: energy-aware scheduling, and classification using ML-based classifiers in conjunction with more reliable but slower deterministic classifiers. It is shown how algorithms using predictions achieve much-improved performance when the low-assurance computations are correct, at a cost of no more than a slight performance degradation even when they turn out to be completely wrong.
Cite as

Kunal Agrawal, Sanjoy Baruah, Michael A. Bender, and Alberto Marchetti-Spaccamela. The Safe and Effective Use of Low-Assurance Predictions in Safety-Critical Systems. In 35th Euromicro Conference on Real-Time Systems (ECRTS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 262, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.ECRTS.2023.3,
  author =	{Agrawal, Kunal and Baruah, Sanjoy and Bender, Michael A. and Marchetti-Spaccamela, Alberto},
  title =	{{The Safe and Effective Use of Low-Assurance Predictions in Safety-Critical Systems}},
  booktitle =	{35th Euromicro Conference on Real-Time Systems (ECRTS 2023)},
  pages =	{3:1--3:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-280-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{262},
  editor =	{Papadopoulos, Alessandro V.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2023.3},
  URN =		{urn:nbn:de:0030-drops-180323},
  doi =		{10.4230/LIPIcs.ECRTS.2023.3},
  annote =	{Keywords: Algorithms using predictions, robust scheduling, energy minimization, classification, on-line scheduling}
}
Document
DOI: 10.4230/LIPIcs.CPM.2021.9
Constructing Strings Avoiding Forbidden Substrings

Authors: Giulia Bernardini, Alberto Marchetti-Spaccamela, Solon P. Pissis, Leen Stougie, and Michelle Sweering

Published in: LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)

Abstract
We consider the problem of constructing strings over an alphabet Σ that start with a given prefix u, end with a given suffix v, and avoid occurrences of a given set of forbidden substrings. In the decision version of the problem, given a set S_k of forbidden substrings, each of length k, over Σ, we are asked to decide whether there exists a string x over Σ such that u is a prefix of x, v is a suffix of x, and no s ∈ S_k occurs in x. Our first result is an 𝒪(|u|+|v|+k|S_k|)-time algorithm to decide this problem. In the more general optimization version of the problem, given a set S of forbidden arbitrary-length substrings over Σ, we are asked to construct a shortest string x over Σ such that u is a prefix of x, v is a suffix of x, and no s ∈ S occurs in x. Our second result is an 𝒪(|u|+|v|+||S||⋅|Σ|)-time algorithm to solve this problem, where ||S|| denotes the total length of the elements of S. Interestingly, our results can be directly applied to solve the reachability and shortest path problems in complete de Bruijn graphs in the presence of forbidden edges or of forbidden paths. Our algorithms are motivated by data privacy, and in particular, by the data sanitization process. In the context of strings, sanitization consists in hiding forbidden substrings from a given string by introducing the least amount of spurious information. We consider the following problem. Given a string w of length n over Σ, an integer k, and a set S_k of forbidden substrings, each of length k, over Σ, construct a shortest string y over Σ such that no s ∈ S_k occurs in y and the sequence of all other length-k fragments occurring in w is a subsequence of the sequence of the length-k fragments occurring in y. Our third result is an 𝒪(nk|S_k|⋅|Σ|)-time algorithm to solve this problem.
Cite as

Giulia Bernardini, Alberto Marchetti-Spaccamela, Solon P. Pissis, Leen Stougie, and Michelle Sweering. Constructing Strings Avoiding Forbidden Substrings. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bernardini_et_al:LIPIcs.CPM.2021.9,
  author =	{Bernardini, Giulia and Marchetti-Spaccamela, Alberto and Pissis, Solon P. and Stougie, Leen and Sweering, Michelle},
  title =	{{Constructing Strings Avoiding Forbidden Substrings}},
  booktitle =	{32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)},
  pages =	{9:1--9:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-186-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{191},
  editor =	{Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.9},
  URN =		{urn:nbn:de:0030-drops-139604},
  doi =		{10.4230/LIPIcs.CPM.2021.9},
  annote =	{Keywords: string algorithms, forbidden strings, de Bruijn graphs, data sanitization}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2021.12
Feasibility Analysis of Conditional DAG Tasks

Authors: Sanjoy Baruah and Alberto Marchetti-Spaccamela

Published in: LIPIcs, Volume 196, 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)

Abstract
Feasibility analysis for Conditional DAG tasks (C-DAGs) upon multiprocessor platforms is shown to be complete for the complexity class pspace. It is shown that as a consequence integer linear programming solvers (ILP solvers) are likely to prove inadequate for such analysis. A demarcation is identified between the feasibility-analysis problems on C-DAGs that are efficiently solvable using ILP solvers and those that are not, by characterizing a restricted class of C-DAGs for which feasibility analysis is shown to be efficiently solvable using ILP solvers.
Cite as

Sanjoy Baruah and Alberto Marchetti-Spaccamela. Feasibility Analysis of Conditional DAG Tasks. In 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 196, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{baruah_et_al:LIPIcs.ECRTS.2021.12,
  author =	{Baruah, Sanjoy and Marchetti-Spaccamela, Alberto},
  title =	{{Feasibility Analysis of Conditional DAG Tasks}},
  booktitle =	{33rd Euromicro Conference on Real-Time Systems (ECRTS 2021)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-192-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{196},
  editor =	{Brandenburg, Bj\"{o}rn B.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2021.12},
  URN =		{urn:nbn:de:0030-drops-139433},
  doi =		{10.4230/LIPIcs.ECRTS.2021.12},
  annote =	{Keywords: Multiprocessor feasibility analysis, Conditional Directed Acyclic Graphs, PSPACE-complete}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.ATMOS.2019
OASIcs, Volume 75, ATMOS'19, Complete Volume

Authors: Valentina Cacchiani and Alberto Marchetti-Spaccamela

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)

Abstract
OASIcs, Volume 75, ATMOS'19, Complete Volume
Cite as

19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Proceedings{cacchiani_et_al:OASIcs.ATMOS.2019,
  title =	{{OASIcs, Volume 75, ATMOS'19, Complete Volume}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019},
  URN =		{urn:nbn:de:0030-drops-114516},
  doi =		{10.4230/OASIcs.ATMOS.2019},
  annote =	{Keywords: Theory of computation, Design and analysis of algorithms; Mathematics of computing, Discrete mathematics; Combinatorics; Mathematical optimization;}
}
Document
Front Matter
DOI: 10.4230/OASIcs.ATMOS.2019.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Valentina Cacchiani and Alberto Marchetti-Spaccamela

Published in: OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cacchiani_et_al:OASIcs.ATMOS.2019.0,
  author =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
  pages =	{0:i--0:x},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-128-3},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{75},
  editor =	{Cacchiani, Valentina and Marchetti-Spaccamela, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.0},
  URN =		{urn:nbn:de:0030-drops-114123},
  doi =		{10.4230/OASIcs.ATMOS.2019.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1815
Nonclairvoyant Speed Scaling for Flow and Energy

Authors: Ho-Leung Chan, Jeff Edmonds, Tak-Wah Lam, Lap-Kei Lee, Alberto Marchetti-Spaccamela, and Kirk Pruhs

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
We study online nonclairvoyant speed scaling to minimize total flow time plus energy. We first consider the traditional model where the power function is $P(s)=s^\alpha$. We give a nonclairvoyant algorithm that is shown to be $O(\alpha^3)$-competitive. We then show an $\Omega( \alpha^{1/3-\epsilon} )$ lower bound on the competitive ratio of any nonclairvoyant algorithm. We also show that there are power functions for which no nonclairvoyant algorithm can be $O(1)$-competitive.
Cite as

Ho-Leung Chan, Jeff Edmonds, Tak-Wah Lam, Lap-Kei Lee, Alberto Marchetti-Spaccamela, and Kirk Pruhs. Nonclairvoyant Speed Scaling for Flow and Energy. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 255-264, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.STACS.2009.1815,
  author =	{Chan, Ho-Leung and Edmonds, Jeff and Lam, Tak-Wah and Lee, Lap-Kei and Marchetti-Spaccamela, Alberto and Pruhs, Kirk},
  title =	{{Nonclairvoyant Speed Scaling for Flow and Energy}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{255--264},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1815},
  URN =		{urn:nbn:de:0030-drops-18151},
  doi =		{10.4230/LIPIcs.STACS.2009.1815},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1338
Minimizing Flow Time in the Wireless Gathering Problem

Authors: Vincenzo Bonifaci, Peter Korteweg, Alberto Marchetti-Spaccamela, and Leen Stougie

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
We address the problem of efficient data gathering in a wireless network through multi-hop communication. We focus on the objective of minimizing the maximum flow time of a data packet. We prove that no polynomial time algorithm for this problem can have approximation ratio less than $Omega(m^{1/3)$ when $m$ packets have to be transmitted, unless $P = NP$. We then use resource augmentation to assess the performance of a FIFO-like strategy. We prove that this strategy is 5-speed optimal, i.e., its cost remains within the optimal cost if we allow the algorithm to transmit data at a speed 5 times higher than that of the optimal solution we compare to.
Cite as

Vincenzo Bonifaci, Peter Korteweg, Alberto Marchetti-Spaccamela, and Leen Stougie. Minimizing Flow Time in the Wireless Gathering Problem. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 109-120, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{bonifaci_et_al:LIPIcs.STACS.2008.1338,
  author =	{Bonifaci, Vincenzo and Korteweg, Peter and Marchetti-Spaccamela, Alberto and Stougie, Leen},
  title =	{{Minimizing Flow Time in the Wireless Gathering Problem}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{109--120},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1338},
  URN =		{urn:nbn:de:0030-drops-13381},
  doi =		{10.4230/LIPIcs.STACS.2008.1338},
  annote =	{Keywords: Wireless networks, data gathering, approximation algorithms, distributed algorithms}
}
Document
DOI: 10.4230/DagSemProc.05031.7
Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm

Authors: Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Guidouca Schaefer, and Tjark Vredeveld

Published in: Dagstuhl Seminar Proceedings, Volume 5031, Algorithms for Optimization with Incomplete Information (2005)

Abstract
In this paper we introduce the notion of smoothed competitive analysis of online algorithms. Smoothed analysis has been proposed by Spielman and Teng to explain the behaviour of algorithms that work well in practice while performing very poorly from a worst case analysis point of view. We apply this notion to analyze the Multi-Level Feedback (MLF) algorithm to minimize the total flow time on a sequence of jobs released over time when the processing time of a job is only known at time of completion. The initial processing times are integers in the range $[1,2^K]$. We use a partial bit randomization model, i.e., the initial processing times are smoothed by changing the $k$ least significant bits under a quite general class of probability distributions. We show that MLF admits a smoothed competitive ratio of $O((2^k/\psigma)^3 + (2^k/\psigma)^2 2^{K-k}})$, where $\sigma$ denotes the standard deviation of the distribution. In particular, we obtain a competitive ratio of $O(2^{K-k})$ if $\sigma = \Theta(2^k)$. We also prove an $\Omega(2^{K-k})$ lower bound for any deterministic algorithm that is run on processing times smoothed according to the partial bit randomization model. For various other smoothing models, including the additive symmetric smoothing one, which is a variant of the model used by Spielman and Teng, we give a higher lower bound of $\Omega(2^K)$. A direct consequence of our result is also the first average case analysis of MLF. We show a constant expected ratio of the total flow time of MLF to the optimum under several distributions including the uniform one.
Cite as

Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Guidouca Schaefer, and Tjark Vredeveld. Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 5-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{becchetti_et_al:DagSemProc.05031.7,
  author =	{Becchetti, Luca and Leonardi, Stefano and Marchetti-Spaccamela, Alberto and Schaefer, Guidouca and Vredeveld, Tjark},
  title =	{{Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{5--28},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.7},
  URN =		{urn:nbn:de:0030-drops-752},
  doi =		{10.4230/DagSemProc.05031.7},
  annote =	{Keywords: Competitive analysis , average case analysis , smoothed analysis , scheduling}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact